package com.whitedust.top60;

import com.whitedust.structure.ListNode;

import java.util.List;

/**
 *
 * @author A
 * @since 2025/11/10 16:37
 */

public class Top56 {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            //核心在于此处必须采用while，因为进行交换之后，然后依旧按照i的顺序以此遍历则会导致漏掉一些数未被处理
            //while能保证所有从i下标访问开始的所有被交换的数最终都在正确的位置上。
            while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {
                int tmp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = tmp;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) return i + 1;
        }
        return nums.length + 1;
    }
}
